package com.wang.transfer.util.algorithm;

/**
 * 删除链表的倒数第n个结点
 * 给一个链表，删除链表的倒数第n个结点，并且返回链表的头结点
 */
public class RemoveNthFromEnd {

    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
//        ListNode listNode5 = new ListNode(5, null);
//        ListNode listNode4 = new ListNode(4, listNode5);
//        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, null);
        ListNode listNode1 = new ListNode(1, listNode2);
        ListNode listNode = new RemoveNthFromEnd().removeNthFromEnd(listNode1, 2);
        System.out.println();
    }

    private static ListNode H;

    /**
     * 100%
     * 官方推荐：创建一个哑结点，就可以不对头结点进行特殊操作了
     * ListNode dummy = new ListNode(0, head)
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head.next == null) {
            return null;
        }
        H = head;
        recursion(null, head, 0, n);
        return H;
    }

    private int recursion(ListNode pre, ListNode node, int i, int n) {
        if (node == null) {
            return 1;
        }
        i = recursion(node, node.next, i, n);
        if (i == n) {
            if (pre == null) {
                H = node.next;
            } else {
                pre.next = node.next;
            }
            return 0;
        }
        if (i == 0) {
            return 0;
        }
        return ++i;
    }
}
